import java.util.ArrayList;
import java.util.List;

class Solution {
    //括号生成
    public List<String> ret;
    public StringBuilder path;
    int left;
    int right;
    int num;
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        left = 0;
        right = 0;
        num = n;
        dfs();
        return ret;
    }

    public void dfs(){
        //递归出口
        if(right >= num){
            ret.add(path.toString());
            return;
        }
        if(left < num){
            left++;
            path.append('(');
            dfs();
            left--;
            path.delete(path.length() - 1, path.length());
        }
        if(right < left){
            right++;
            path.append(')');
            dfs();
            right--;
            path.delete(path.length() - 1, path.length());
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.generateParenthesis(1);
        System.out.println(solution.generateParenthesis(1));
    }
}